package cczxsong;

import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.StdOut;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.InputStreamReader;

class BoyerMoore {
    private final int R;
    private int[] right;
    private String pat;

    public BoyerMoore(String pat) {
        this.R = 256;
        this.pat = pat;

        right = new int[R];
        for (int c = 0; c < R; c++)
            right[c] = -1;
        for (int j = 0; j < pat.length(); j++)
            right[pat.charAt(j)] = j;
    }

    public int search(String txt) {
        int m = pat.length();
        int n = txt.length();
        int skip;
        for (int i = 0; i <= n - m; i += skip) {
            skip = 0;
            for (int j = m - 1; j >= 0; j--) {
                if (pat.charAt(j) != txt.charAt(i + j)) {
                    skip = Math.max(1, j - right[txt.charAt(i + j)]);
                    break;
                }
            }
            if (skip == 0) return i;//找到了 返回第一个字符的位置
        }
        return -1; //没找到 返回-1
    }

    public int searchPos(String txt, int n) {
        int count = 0;
        char[] tx = txt.toCharArray();
        for (int i = 0; i < n; i++) {
            if (tx[i] == ' ') count++;
        }
        return count;
    }
}

public class Exp_string {
    public static void main(String[] args) {
        String txt1 = readTxt();
//        StdOut.println(txt1);
//        File file = new File("C:\\Users\\王\\Desktop\\ppm1.txt");
        File file = new File("C:\\Users\\王\\Desktop\\ppm2.txt");
        FileInputStream is = null;
        try {
            if (file.length() != 0) {
                is = new FileInputStream(file);
                InputStreamReader streamReader = new InputStreamReader(is);
                BufferedReader reader = new BufferedReader(streamReader);
                String line;
                while ((line = reader.readLine()) != null) {
                    BoyerMoore boyermoore = new BoyerMoore(line);
                    int offset = boyermoore.search(txt1);
                    if (offset == -1) StdOut.println("-- "+line);//没找到
                    else {
                        int pos = boyermoore.searchPos(txt1,offset);
                        StdOut.print(pos+1);
                        StdOut.println(' '+line);
                    }
                }
                reader.close();
                is.close();
            } else {
                StdOut.println("文件为空");
            }
        } catch (Exception e) {
            e.printStackTrace();
        }
    }

    public static String readTxt() {
//        File file = new File("C:\\Users\\王\\Desktop\\test1.txt");
        File file = new File("C:\\Users\\王\\Desktop\\test2.txt");
        FileInputStream is = null;
        StringBuilder stringBuilder = null;
        try {
            if (file.length() != 0) {
                is = new FileInputStream(file);
                InputStreamReader streamReader = new InputStreamReader(is);
                BufferedReader reader = new BufferedReader(streamReader);
                String line;
                stringBuilder = new StringBuilder();
                while ((line = reader.readLine()) != null) {
                    stringBuilder.append(line);
                    stringBuilder.append(' ');
                }
                reader.close();
                is.close();
            } else {
                StdOut.println("文件为空");
            }

        } catch (Exception e) {
            e.printStackTrace();
        }
        return String.valueOf(stringBuilder);
    }
}
